package leetcode.editor.cn.dsa12_divideAndConquer;
//给定一个大小为 n 的数组，找到其中的多数元素

public class MajorityElement169_1 {
    public static void main(String[] args) {
        Solution solution = new MajorityElement169_1().new Solution();
        int[] arr = {3,2,3};
        System.out.println(solution.majorityElement(arr));
        int[] arr2 = {2,2,1,1,1,2,2};
        System.out.println(solution.majorityElement(arr2));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int majorityElement(int[] nums) {
            // 根据题意：多数元素的个数总和 > 其他所有元素的个数总和
            // 从第一个数开始计数，遇到相同的就加1，遇到不同的就减1
            // 减到0就重新换个数开始计数，最后在计数的那个数就是多数元素
            int count = 1;
            int target = nums[0];
            for (int num : nums) {
                if (num == target) {
                    count++;
                } else {
                    count--;
                    if (count == 0) {
                        count = 1;
                        target = num;
                    }
                }
            }
            return target;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}